#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/* merge arr[begin..mid] and arr[mid+1..end] */
void
merge(int *arr, int begin, int mid, int end)
{
	int *first, *second;
	int first_num = mid-begin+1;
	int second_num = end-mid;
	int i, j, k;

	if((first = calloc(first_num, sizeof(int))) == NULL) {
		fprintf(stderr, "calloc error in merge\n");
		exit(1);
	}
	if((second = calloc(second_num, sizeof(int))) == NULL) {
		fprintf(stderr, "calloc error in merge\n");
		exit(1);
	}

	memcpy(first, arr+begin, first_num*sizeof(int));
	memcpy(second, arr+mid+1, second_num*sizeof(int));

	i = j = 0;
	k = begin;
	while(i<first_num && j<second_num) {
		if(first[i] <= second[j])
			arr[k++] = first[i++];
		else
			arr[k++] = second[j++];
	}
	if(i == first_num)
		for( ; j<second_num; j++)
			arr[k++] = second[j];
	else
		for( ; i<first_num; i++)
			arr[k++] = first[i];

	free(first);
	free(second);
}

/* for array[n], call merge_sort(array, 0, n-1) */
void
merge_sort(int *arr, int begin, int end)
{
	if(begin >= end)
		return;
	
	int mid = (begin+end)/2;
	merge_sort(arr, begin, mid);
	merge_sort(arr, mid+1, end);

	merge(arr, begin, mid, end);
}
